﻿using System;
using Algoritmia.DataStructures.Lists;
using Algoritmia.Utils;

namespace Algoritmia.Problems.Searching
{
    public class ThresholdedBinarySearcher<T> : ISortedSearcher<T>
    {
        private readonly int _threshold;
        private Comparison<T> _comparison;

        public ThresholdedBinarySearcher(int threshold = 3)
        {
            _threshold = threshold;
        }

        #region ISortedSearcher<T> Members

        public int IndexOf(IList<T> list, T elem, Comparison<T> comparison = null)
        {
            _comparison = AlgoritmiaFactory.GetDefaultComparison(comparison);
            Func<int, int, int> f = null;
            f = (first, last) =>
                    {
                        if (last - first <= _threshold)
                        {
                            for (int i = first; i <= last; i++)
                            {
                                if (_comparison(list[i], elem) == 0)
                                {
                                    return i;
                                }
                            }
                            return -1;
                        }

                        int pivot = (first + last)/2;
                        if (_comparison(elem, list[pivot]) < 0)
                        {
                            last = pivot;
                        }
                        else if (_comparison(elem, list[pivot]) > 0)
                        {
                            first = pivot + 1;
                        }
                        else
                        {
                            return pivot;
                        }

                        return f(first, last);
                    };
            return f(0, list.Count - 1);
        }


        #endregion
    }
}
